#include <stdio.h>

#include "bitree.h"

int cnt = 0;

// 递归先序遍历统计叶子结点数
void PreOrderCount(BiTree t) {
    if (!t) return;
    if (!t->lchild && !t->rchild) {
        ++cnt;
    }
    PreOrderCount(t->lchild);
    PreOrderCount(t->rchild);
}

// 递归中序遍历统计叶子结点数
void InOrderCount(BiTree t) {
    if (!t) return;
    InOrderCount(t->lchild);
    if (!t->lchild && !t->rchild) {
        ++cnt;
    }
    InOrderCount(t->rchild);
}

// 递归后序遍历统计叶子结点数
void PostOrderCount(BiTree t) {
    if (!t) return;
    PostOrderCount(t->lchild);
    PostOrderCount(t->rchild);
    if (!t->lchild && !t->rchild) {
        ++cnt;
    }
}

// 层次遍历统计叶子结点数
void LevelOrderCount(BiTree t) {
    if (!t) {
        return;  // 空树直接返回
    }
    SqQueue q;
    InitQueue(&q);
    EnQueue(&q, t);
    while (!QueueEmpty(&q)) {
        BiTree p;
        DeQueue(&q, (void**)&p);
        if (!p->lchild && !p->rchild) {
            ++cnt;
        }
        if (p->lchild) {
            EnQueue(&q, p->lchild);  // 如果有左孩子，将左孩子入队
        }
        if (p->rchild) {
            EnQueue(&q, p->rchild);  // 如果有右孩子，将右孩子入队
        }
    }
}

void TestLeafCnt(ElemType arr[], int n) {
    printf("test begin\n");

    BiTree root;
    LevelOrderCreateBiTree(&root, arr, n);

    struct {
        char* name;
        void (*visit)(BiTree);
    } testFunc[] = {{"先序遍历", PreOrderCount},
                    {"中序遍历", InOrderCount},
                    {"后序遍历", PostOrderCount},
                    {"层序遍历", LevelOrderCount}};

    for (int i = 0; i < sizeof(testFunc) / sizeof(testFunc[0]); ++i) {
        cnt = 0;
        printf("%s: ", testFunc[i].name);
        testFunc[i].visit(root);
        printf("%d\n", cnt);
    }

    printf("test end\n");
}

int main() {
    ElemType arr1[] = {'A'};
    TestLeafCnt(arr1, 1);

    ElemType arr2[] = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
    TestLeafCnt(arr2, 7);

    ElemType arr3[] = {'A', 'B', 'C', '#', '#', 'D', 'E', '#',
                       'F', '#', '#', 'G', '#', '#', '#'};
    TestLeafCnt(arr3, 15);

    return 0;
}